{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Wildcard Matching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #recursion #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #递归 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isMatch"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #通配符匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<div class=\"title__3Vvk\">给你一个输入字符串 (<code>s</code>) 和一个字符模式 (<code>p</code>) ，请你实现一个支持 <code>'?'</code> 和 <code>'*'</code> 匹配规则的通配符匹配：</div>\n",
    "\n",
    "<ul>\n",
    "\t<li class=\"title__3Vvk\"><code>'?'</code> 可以匹配任何单个字符。</li>\n",
    "\t<li class=\"title__3Vvk\"><code>'*'</code> 可以匹配任意字符序列（包括空字符序列）。</li>\n",
    "</ul>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p>判定匹配成功的充要条件是：字符模式必须能够 <strong>完全匹配</strong> 输入字符串（而不是部分匹配）。</p>\n",
    "</div>\n",
    "</div>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aa\", p = \"a\"\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>\"a\" 无法匹配 \"aa\" 整个字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aa\", p = \"*\"\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>'*' 可以匹配任意字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"cb\", p = \"?a\"\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= s.length, p.length &lt;= 2000</code></li>\n",
    "\t<li><code>s</code> 仅由小写英文字母组成</li>\n",
    "\t<li><code>p</code> 仅由小写英文字母、<code>'?'</code> 或 <code>'*'</code> 组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [wildcard-matching](https://leetcode.cn/problems/wildcard-matching/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [wildcard-matching](https://leetcode.cn/problems/wildcard-matching/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aa\"\\n\"a\"', '\"aa\"\\n\"*\"', '\"cb\"\\n\"?a\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        @cache\n",
    "        def isMatchHelper(i, j):\n",
    "            if i < -1 or j < -1:\n",
    "                return False\n",
    "            if i == -1 and j == -1: # s = \"ab\", p = \"ab\"\n",
    "                return True\n",
    "            if j == -1: # s = \"ab\", p = \"\"\n",
    "                return False\n",
    "            if p[j] == '*': # s = \"ab\", p = \"*\" or s = \"\", p = \"*********\"\n",
    "                return isMatchHelper(i - 1, j) or isMatchHelper(i, j - 1)\n",
    "            if i == -1: # s = \"\", p = \"ab\"\n",
    "                return False\n",
    "            if p[j] == '?': # s = \"ab\", p = \"a?\"\n",
    "                return isMatchHelper(i - 1, j - 1)\n",
    "            if s[i] == p[j]: # s = \"ab\", p = \"ab\"\n",
    "                return isMatchHelper(i - 1, j - 1)\n",
    "            return False # s = \"a\", p = \"b\"\n",
    "            \n",
    "        return isMatchHelper(len(s) - 1, len(p) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s, p):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type p: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        ls = len(s)\n",
    "        lp = len(p)\n",
    "        #When substring of p is zero only when s is zero the result is True\n",
    "        DP = [True] + [False] * ls\n",
    "        for i in range(lp):\n",
    "            if p[i] != '*':\n",
    "                for j in range(ls - 1, -1, -1):\n",
    "                    #When p[i] is not *, then relies on (i-1,j-1) and p[i] == s[j]\n",
    "                    DP[j + 1] = DP[j] and (p[i] == s[j] or p[i] == '?')\n",
    "                DP[0] = False\n",
    "            else:\n",
    "                for j in range(1, ls + 1):\n",
    "                    DP[j] = DP[j - 1] or DP[j]\n",
    "        return DP[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        scur, pcur, sstar, pstar = 0, 0, None, None\n",
    "\n",
    "        while scur < len(s):\n",
    "            if pcur < len(p) and p[pcur] in [s[scur], '?']:\n",
    "                scur, pcur = scur+1, pcur+1\n",
    "            elif pcur < len(p) and p[pcur] == '*':\n",
    "                pstar, pcur = pcur, pcur+1\n",
    "                sstar = scur\n",
    "            elif pstar != None:\n",
    "                pcur = pstar + 1\n",
    "                sstar += 1\n",
    "                scur = sstar\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        while pcur < len(p) and p[pcur] == '*':\n",
    "            pcur += 1\n",
    "\n",
    "        return pcur >= len(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        m=len(s)\n",
    "        dic=[True]+[False]*m\n",
    "        for i in p:\n",
    "            if i=='*':\n",
    "                for j in range(1,m+1):\n",
    "                    dic[j]=dic[j-1] or dic[j]\n",
    "            else:\n",
    "                for j in range(m,0,-1):\n",
    "                    dic[j]=dic[j-1] and (i=='?' or i==s[j-1])\n",
    "            dic[0]=dic[0] and i=='*'\n",
    "        return dic[-1]\n",
    "                \n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        lens, lenp = len(s), len(p)\n",
    "        i, j = 0, 0\n",
    "        start, match = -1, 0\n",
    "\n",
    "        while i < lens:\n",
    "            # \"?\"\n",
    "            if j < lenp and (s[i] == p[j] or p[j] == \"?\"):\n",
    "                i += 1\n",
    "                j += 1\n",
    "            elif j < lenp and p[j] == \"*\":\n",
    "                start = j\n",
    "                match = i\n",
    "                j += 1\n",
    "            elif start != -1:\n",
    "                j = start + 1\n",
    "                match += 1\n",
    "                i = match\n",
    "            else:\n",
    "                return False\n",
    "        return all(c == \"*\" for c in p[j:])\n",
    "\n",
    "\n",
    "            # \"*\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        # recursion base: s(0, 0) = True\n",
    "        # recursion base: s(m, 0) = False, m neq 0\n",
    "        # transformation equation:\n",
    "        # case 1: p[n - 1] == s[m - 1] || p[n - 1] == \"?\": s(m, n) = s(m - 1, n - 1)\n",
    "        # case 2: p[n - 1] == \"*\": s(m, n) = any(s(*, n - 1))\n",
    "        m, n = len(s), len(p)\n",
    "        prev = [True] + [False] * n\n",
    "        curr = [False] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            prev[i] = p[i - 1] == \"*\" and prev[i - 1]\n",
    "        for i in range(1, m + 1):\n",
    "            curr[0] = False\n",
    "            for j in range(1, n + 1):\n",
    "                if p[j - 1] == s[i - 1] or p[j - 1] == \"?\":\n",
    "                    curr[j] = prev[j - 1]\n",
    "                else:\n",
    "                    curr[j] = p[j - 1] == \"*\" and (curr[j - 1] or prev[j])\n",
    "            prev, curr = curr, prev\n",
    "        return prev[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        def chmatch(a,b):\n",
    "            return a==b or b=='?'\n",
    "        if(s==p):\n",
    "            return True\n",
    "        if(len(p)==0):\n",
    "            return False\n",
    "        if p =='*':\n",
    "            return True\n",
    "        sr,pr=len(s),len(p)\n",
    "        while(sr>0 and pr>0 and p[pr-1]!='*'):\n",
    "            if(chmatch(s[sr-1],p[pr-1])):\n",
    "                sr-=1\n",
    "                pr-=1\n",
    "            else:\n",
    "                return False\n",
    "        if(pr==0):\n",
    "            return sr==0\n",
    "        sl,pl=0,0\n",
    "        sd,pd=-1,-1\n",
    "        while sl<sr and pl<pr:\n",
    "            if(p[pl]=='*'):\n",
    "                pl+=1\n",
    "                sd,pd=sl,pl\n",
    "            elif(chmatch(s[sl],p[pl])):\n",
    "                sl+=1\n",
    "                pl+=1\n",
    "            elif(sd!=-1 and sd+1<sr):\n",
    "                sd+=1\n",
    "                sl,pl=sd,pd\n",
    "            else:\n",
    "                return False\n",
    "        for i in range(pl,pr):\n",
    "            if(p[i]!='*'):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=44 lang=python3\n",
    "#\n",
    "# [44] 通配符匹配\n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def removeDulicatedStar(self, p):\n",
    "        if not p:\n",
    "            return p\n",
    "        # p == '*'\n",
    "        ans = [p[0]]\n",
    "        for i in range(1, len(p)):\n",
    "            if p[i] == \"*\" and p[i] == p[i - 1]:\n",
    "                continue\n",
    "            ans.append(p[i])\n",
    "        return ''.join(ans)\n",
    "    \n",
    "\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        p = self.removeDulicatedStar(p)\n",
    "        @lru_cache\n",
    "        def dp(i, j):\n",
    "            if j == len(p) - 1 and p[j] == '*': return True\n",
    "            if j >= len(p): return i >= len(s)\n",
    "            if i >= len(s): return j >= len(p)\n",
    "            first_match = s[i] == p[j] or p[j] == '?' or p[j] == '*'\n",
    "\n",
    "            if not first_match:\n",
    "                return False\n",
    "            if p[j] == '?' or s[i] == p[j]:\n",
    "                return dp(i+1, j + 1)\n",
    "            if p[j] == '*':\n",
    "                return dp(i, j + 1) or dp(i + 1, j)\n",
    "        return dp(0, 0)\n",
    "\n",
    "# @lc code=end\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDulicatedStar(self, p):\n",
    "        if not p:\n",
    "            return p\n",
    "        # p == '*'\n",
    "        ans = [p[0]]\n",
    "        for i in range(1, len(p)):\n",
    "            if p[i] == \"*\" and p[i] == p[i - 1]:\n",
    "                continue\n",
    "            ans.append(p[i])\n",
    "        return ''.join(ans)\n",
    "    @lru_cache\n",
    "    def helper(self, s, p):\n",
    "        if p == '*': return True\n",
    "        if not p:\n",
    "            return not s\n",
    "        if not s:\n",
    "            return not p\n",
    "        first_match = s[0] == p[0] or p[0] == '?' or p[0] == '*'\n",
    "\n",
    "        if not first_match:\n",
    "            return False\n",
    "        if p[0] == '?' or s[0] == p[0]:\n",
    "            return self.helper(s[1:], p[1:])\n",
    "        if p[0] == '*':\n",
    "            return self.helper(s, p[1:]) or self.helper(s[1:], p)\n",
    "\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        return self.helper(s, self.removeDulicatedStar(p))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i:int, j:int)->bool:\n",
    "            if i == len(s) and j == len(p):\n",
    "                return True\n",
    "            acount = p[j:].count('*')\n",
    "            if len(p) - acount - j > len(s) - i:\n",
    "                return False\n",
    "            if acount == 0 and len(p) - j != len(s) - i:\n",
    "                return False\n",
    "\n",
    "            if i == len(s):\n",
    "                if p[j] != '*':\n",
    "                    return False\n",
    "                return dfs(i, j + 1)\n",
    "            if j == len(p):\n",
    "                return False\n",
    "            if p[j] == '?':\n",
    "                return dfs(i + 1 , j + 1)\n",
    "            if p[j] == '*':\n",
    "                for k in range(i, len(s)+1):\n",
    "                    if dfs(k, j + 1):\n",
    "                        return True\n",
    "                return False\n",
    "            if s[i] == p[j]:\n",
    "                return dfs(i+1, j+1)\n",
    "            return False\n",
    "        \n",
    "        if p and s and p[-1] != '*' and p[-1] != '?' and p[-1] != s[-1]:\n",
    "            return False\n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        # dp[i][j] denotes whether s[:i] could be represented by p[:j]\n",
    "        dp = [[False for _ in range(len(p) + 1)] for _ in range(len(s) + 1)]\n",
    "        dp[0][0] = True\n",
    "        for j in range(1, len(p) + 1):\n",
    "            if p[j-1] == \"*\":\n",
    "                dp[0][j] = dp[0][j-1]\n",
    "        for i in range(1, len(s) + 1):\n",
    "            for j in range(1, len(p) + 1):\n",
    "                if s[i-1] == p[j-1] or p[j-1] == \"?\":\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                elif p[j-1] == \"*\":\n",
    "                    for k in range(i, -1, -1):\n",
    "                        dp[i][j] = dp[i][j] or dp[k][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = False\n",
    "        return dp[len(s)][len(p)]\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        zong = len(p)+1 #纵轴长度\n",
    "        heng = len(s)+1 #横轴长度\n",
    "        # 优化：只初始化第一行中 * 的数量个元素为 True，其余为 False\n",
    "        table = [[False] * heng for _ in range(zong)]\n",
    "        table[0][0] = True\n",
    "        \n",
    "        for m in range(1, zong):\n",
    "            if p[m - 1] == '*':\n",
    "                table[m][0] = table[m - 1][0]  # 匹配空字符串\n",
    "\n",
    "            path = False\n",
    "            for n in range(1, heng):\n",
    "                if p[m - 1] == '*':\n",
    "                    if table[m - 1][0]:\n",
    "                        table[m] = [True] * heng\n",
    "                    if table[m - 1][n]:\n",
    "                        path = True\n",
    "                    if path:\n",
    "                        table[m][n] = True\n",
    "                elif p[m - 1] == '?' or p[m - 1] == s[n - 1]:\n",
    "                    table[m][n] = table[m - 1][n - 1]\n",
    "\n",
    "\n",
    "        return table[zong - 1][heng - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        if s == '' and p == '':\n",
    "            return True\n",
    "        m, n = len(s), len(p)\n",
    "        dp = [[False] * (n + 1) for _ in range(m + 1)]\n",
    "        dp[0][0] = True\n",
    "        for j in range(1, n + 1):\n",
    "            if p[j - 1] == '*':\n",
    "                dp[0][j] = True\n",
    "            else:\n",
    "                break\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if s[i-1] == p[j-1] or p[j-1] == '?':\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                elif p[j-1] == '*':\n",
    "                    dp[i][j] = dp[i][j-1] or dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = False\n",
    "        return dp[m][n] \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        if not p:\n",
    "            return not s\n",
    "        # 将 p 中相邻的 * 去除，以提升效率\n",
    "        pp = self.remove_adj_star(p)\n",
    "        m, n = len(s), len(pp)\n",
    "        # 备忘录初始化为 -1\n",
    "        memo = [[-1] * n for _ in range(m)]\n",
    "        # 执行自顶向下带备忘录的动态规划\n",
    "        return self.dp(s, 0, pp, 0, memo)\n",
    "\n",
    "    # 删除相邻的 * 号，返回删除后的字符\n",
    "    def remove_adj_star(self, p: str) -> str:\n",
    "        if not p:\n",
    "            return \"\"\n",
    "        pp = p[0]\n",
    "        for i in range(1, len(p)):\n",
    "            if p[i] == '*' and p[i - 1] == '*':\n",
    "                continue\n",
    "            pp += p[i]\n",
    "        return pp\n",
    "\n",
    "    # 定义：判断 s[i..] 是否能被 p[j..] 匹配\n",
    "    def dp(self, s: str, i: int, p: str, j: int, memo: List[List[int]]) -> bool:\n",
    "        # base case\n",
    "        if j == len(p) and i == len(s):\n",
    "            return True\n",
    "        if i == len(s):\n",
    "            for k in range(j, len(p)):\n",
    "                if p[k] != '*':\n",
    "                    return False\n",
    "            return True\n",
    "        if j == len(p):\n",
    "            return False\n",
    "        if memo[i][j] != -1:\n",
    "            return bool(memo[i][j])\n",
    "\n",
    "        res = False\n",
    "        if s[i] == p[j] or p[j] == '?':\n",
    "            # s[i] 和 p[j] 完成匹配\n",
    "            res = self.dp(s, i + 1, p, j + 1, memo)\n",
    "        elif p[j] == '*':\n",
    "            # s[i] 和 p[j] 不匹配，但 p[j] 是通配符 *\n",
    "            # 可以匹配 0 个或多个 s 中的字符，\n",
    "            # 只要有一种情况能够完成匹配即可\n",
    "            res = self.dp(s, i + 1, p, j, memo) or self.dp(s, i, p, j + 1, memo)\n",
    "        # 将 s[i] 和 p[j] 的匹配结果存储备忘录\n",
    "        memo[i][j] = res\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        # 深度优先搜索：往后看\n",
    "        n, m = len(s), len(p)\n",
    "        memo = [[-1] * m for _ in range(n + 1)]\n",
    "\n",
    "        def dfs(i: int, j: int):\n",
    "\n",
    "            if j == m:\n",
    "                return i == n\n",
    "\n",
    "            if memo[i][j] != -1:\n",
    "                return memo[i][j]\n",
    "            \n",
    "            if p[j] == \"*\":\n",
    "                memo[i][j] = (i < len(s) and dfs(i + 1, j)) or dfs(i, j + 1)\n",
    "            else:\n",
    "                memo[i][j] = i < len(s) and dfs(i + 1, j + 1) and p[j] in {s[i], \"?\"}\n",
    "            return memo[i][j]\n",
    "        return dfs(0, 0)\n",
    "\n",
    "        # # 动态规划\n",
    "        # # 横轴为p, 纵轴为s\n",
    "        # n, m = len(s), len(p)\n",
    "        # dp = [[False] * (n + 1) for _ in range(m + 1)]\n",
    "        # dp[0][0] = True\n",
    "        # for i in range(1, m + 1):\n",
    "        #     if p[i - 1] == \"*\":\n",
    "        #         dp[i][0] = dp[i - 1][0]\n",
    "\n",
    "        # for i in range(1, m + 1):\n",
    "        #     for j in range(1, n + 1):\n",
    "        #         if p[i - 1] == \"*\":\n",
    "        #             dp[i][j] = dp[i][j - 1] or dp[i - 1][j]\n",
    "        #         else:\n",
    "        #             dp[i][j] = dp[i - 1][j - 1] and p[i - 1] in {s[j - 1], \"?\"}\n",
    "        # return dp[m][n]\n",
    "\n",
    "        # # 空间优化 + 提前停止\n",
    "        # # 横轴为s, 纵轴为p\n",
    "        # n, m = len(s), len(p)\n",
    "        # dp = [False] * (m + 1)\n",
    "        # dp[0] = True\n",
    "        # for j in range(1, m + 1):\n",
    "        #     if p[j - 1] == \"*\":\n",
    "        #         dp[j] = dp[j - 1]\n",
    "\n",
    "        # for i in range(1, n + 1):\n",
    "        #     dp2 = [False] * (m + 1)\n",
    "        #     for j in range(1, m + 1):\n",
    "        #         if p[j - 1] == \"*\":\n",
    "        #             dp2[j] = dp2[j - 1] or dp[j]\n",
    "        #         else:\n",
    "        #             dp2[j] = dp[j - 1] and p[j - 1] in {\"?\", s[i - 1]}\n",
    "            \n",
    "        #     dp = dp2\n",
    "        #     if sum(dp) == 0:\n",
    "        #         return False\n",
    "        # return dp[m]\n",
    "\n",
    "        # # 动态规划\n",
    "        # # 横轴为s, 纵轴为p\n",
    "        # n, m = len(s), len(p)\n",
    "        # dp = [[False] * (m + 1) for _ in range(n + 1)]\n",
    "        # dp[0][0] = True\n",
    "        # for j in range(1, m + 1):\n",
    "        #     if p[j - 1] == \"*\":\n",
    "        #         dp[0][j] = dp[0][j - 1]\n",
    "\n",
    "        # for i in range(1, n + 1):\n",
    "        #     for j in range(1, m + 1):\n",
    "        #         if p[j - 1] == \"*\":\n",
    "        #             dp[i][j] = dp[i][j - 1] or (dp[i - 1][j])\n",
    "        #         else:\n",
    "        #             dp[i][j] = dp[i - 1][j - 1] and p[j - 1] in {s[i - 1], \"?\"}\n",
    "        # return dp[n][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        # 定义dp[i][j]为p的前i个字符，和s的前j个字符是否匹配\n",
    "        # dp[i][j] 根据末尾字符串分情况讨论\n",
    "        # 结果dp[m][n]\n",
    "        m = len(p)\n",
    "        n = len(s)\n",
    "        dp = [[0] * (n+1) for _ in range(m+1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, m+1):\n",
    "            p_set = set(p[:i])\n",
    "            if len(p_set) == 1 and '*' in p_set:\n",
    "                dp[i][0] = 1\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if p[i-1] == '*':\n",
    "                    dp[i][j] = max(dp[i] + [dp[i-1][j]])\n",
    "                elif p[i-1] == '?':\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    if p[i-1] == s[j-1]:\n",
    "                        dp[i][j] = dp[i-1][j-1]\n",
    "        print(dp)\n",
    "        return True if dp[m][n] == 1 else False\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        # dp abcbca, a*?ca\n",
    "        # 1 0 0 0 0 0 a\n",
    "        # 1 1 1 1 1 1 *\n",
    "        # 0 1 1 1 1 1 ?\n",
    "        # 0 0 1 0 1 0 c\n",
    "        # 0 0 0 0 0 1 a\n",
    "\n",
    "        dp = [[0]*(len(s)+1) for _ in range(len(p)+1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,len(p)+1):\n",
    "            for j in range(0,len(s)+1):\n",
    "                if p[i-1] == '*':\n",
    "                    if dp[i-1][j] or j > 0 and (dp[i][j-1] or dp[i-1][j-1] == 1):\n",
    "                        dp[i][j] = 1\n",
    "                elif p[i-1] == '?':\n",
    "                   # print(\"here\")\n",
    "                    dp[i][j] = dp[i-1][j-1] if j > 0 else 0\n",
    "                    #print(dp[i][j], i, j)\n",
    "                else:\n",
    "                    if j > 0 and s[j-1] == p[i-1] and dp[i-1][j-1]:\n",
    "                        dp[i][j] = 1\n",
    "        print(dp)\n",
    "        return dp[-1][-1] == 1\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        map=[[0 for _ in range(len(s)+1)] for _ in range(len(p)+1)]\n",
    "        map[0][0]=1\n",
    "        for i in range(1,len(p)+1):\n",
    "            if len(s)==0:\n",
    "                if map[i-1][0]==1:\n",
    "                    if p[i-1]=='*':\n",
    "                        map[i][0]=1\n",
    "                continue\n",
    "            for j in range(len(s)):\n",
    "                if map[i-1][j]==1:\n",
    "                    if p[i-1]==s[j]:\n",
    "                        map[i][j+1]=1\n",
    "                    elif p[i-1]=='*':\n",
    "                        for k in range(j,len(s)+1):\n",
    "                            map[i][k]=1\n",
    "                    elif p[i-1]=='?':\n",
    "                        map[i][j+1]=1\n",
    "            if map[i-1][len(s)]==1 and p[i-1]=='*':\n",
    "                map[i][len(s)]=1\n",
    "        print(map)\n",
    "        return map[len(p)][len(s)]==1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        dp = np.zeros(\n",
    "            shape = (len(s) + 1, len(p) + 1),\n",
    "            dtype = bool\n",
    "        )\n",
    "\n",
    "        dp[0][0] = True\n",
    "        # dp[i][0] (i > 0) 均为 False\n",
    "        # dp[0][j] (j > 0) 需要判断\n",
    "\n",
    "        for j in range(1, len(p) + 1):\n",
    "            if p[j - 1] == '*':\n",
    "                dp[0][j] = dp[0][j - 1]\n",
    "        \n",
    "        for j in range(1, len(p) + 1):\n",
    "            for i in range(1, len(s) + 1):\n",
    "                if p[j - 1] == '*':\n",
    "                    dp[i][j] = dp[i][j - 1] or dp[i - 1][j]\n",
    "                elif (p[j - 1] == '?') or (p[j - 1] == s[i - 1]):\n",
    "                    dp[i][j] = dp[i - 1][j - 1]\n",
    "        return bool(dp[-1][-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def finditer_overlapping(pattern: str, string: str) -> Generator[Tuple[int, int], None, None]:\n",
    "    for start in range(len(string)):\n",
    "        if (match_ := match('.{' + str(start) + '}' + pattern, string)) is not None:\n",
    "            yield match_.start() + start, match_.end()\n",
    "\n",
    "def match_star(s: str, p: str) -> bool:\n",
    "    return len(s) == 0 or len(p) > 0\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        for match in finditer(r'[^*]+', p):\n",
    "            char = match.group()\n",
    "            start = match.start()\n",
    "            end = match.end()\n",
    "            for s_start, s_end in finditer_overlapping(char.replace('?', '.'), s):\n",
    "                if match_star(s[:s_start], p[:start]) and self.isMatch(s[s_end:], p[end:]):\n",
    "                \treturn True\n",
    "            return False\n",
    "        return match_star(s, p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        \n",
    "        ans = 0\n",
    "        memo = defaultdict()\n",
    "        def fun(i, j, s, p, n, m):\n",
    "            if (i,j) in memo:\n",
    "                return memo[(i,j)]\n",
    "            if i == n:\n",
    "                if j == m:\n",
    "                    memo[(i,j)] = True\n",
    "                    return True\n",
    "                else:\n",
    "                    while j < m:\n",
    "                        if p[j] != '*':\n",
    "                            memo[(i,j)] = False\n",
    "                            return False\n",
    "                        j += 1\n",
    "                    memo[(i,j)] = True\n",
    "                    return True\n",
    "            if j == m:\n",
    "                memo[(i,j)] = False\n",
    "                return False\n",
    "            if s[i] == p[j]:\n",
    "                return fun(i+1, j+1, s, p, n, m)\n",
    "            else:\n",
    "                if p[j] == '?':\n",
    "                    return fun(i+1, j+1, s, p, n, m)\n",
    "                elif p[j] == '*':\n",
    "                    if fun(i, j+1, s, p, n, m) or fun(i+1, j, s, p, n, m):\n",
    "                        memo[(i,j)] = True\n",
    "                        return True\n",
    "                    memo[(i,j)] = False\n",
    "                    return False\n",
    "                else:\n",
    "                    memo[(i,j)] = False\n",
    "                    return False\n",
    "\n",
    "        \n",
    "        ans = fun(0, 0, s, p, len(s), len(p))\n",
    "        #print(memo)\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def finditer_overlapping(pattern: str, string: str) -> Generator[Tuple[int, int], None, None]:\n",
    "    result = []\n",
    "    for start in range(len(string)):\n",
    "        if (match_ := match('.{' + str(start) + '}' + pattern, string)) is not None:\n",
    "            result.append(match_.end())\n",
    "    return result\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        @cache\n",
    "        def is_match(s: str, p: str) -> bool:\n",
    "            s_match = search(r'[^*]+', p)\n",
    "            if s_match is None:\n",
    "                return len(s) == 0 or len(p) > 0\n",
    "            char = s_match.group()\n",
    "            start = s_match.start()\n",
    "            end = s_match.end()\n",
    "            if start == 0:\n",
    "                s_match = match(char.replace('?', '.'), s)\n",
    "                if s_match is None:\n",
    "                    return False\n",
    "                return is_match(s[s_match.end():], p[end:])\n",
    "            for s_end in finditer_overlapping(char.replace('?', '.'), s):\n",
    "                if is_match(s[s_end:], p[end:]):\n",
    "                \treturn True\n",
    "            return False\n",
    "        return is_match(s, re.sub(r'\\*{2,}', '*', p))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        # print (s, p)\n",
    "        m = len(s)\n",
    "        n = len(p)\n",
    "\n",
    "        if (n == 0):\n",
    "            return m == 0\n",
    "\n",
    "        if (m == 0):\n",
    "            for c in p:\n",
    "                if (c != '*'):\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while(i < m and j < n):\n",
    "            if (s[i] == p[j] or p[j] == '?'):\n",
    "                i += 1\n",
    "                j += 1\n",
    "                continue\n",
    "\n",
    "            if (p[j] != '*'):\n",
    "                return False\n",
    "\n",
    "            cnt = 0\n",
    "            while (p[j] == '*' or p[j] == '?'):\n",
    "                if (p[j] == '?'):\n",
    "                    cnt += 1\n",
    "                j += 1\n",
    "                if (j >= n):\n",
    "                    return (m-i) >= cnt\n",
    "            # print(i, j, m, n, cnt)\n",
    "            \n",
    "            for k in range(i+cnt, m):\n",
    "                if (s[k] == p[j] and self.isMatch(s[k:], p[j:])):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        # print(i, j, m, n)    \n",
    "        if (i >= m):\n",
    "            if (j == n):\n",
    "                return True\n",
    "            for k in range(j, n):\n",
    "                if (p[k] != '*'):\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        import numpy as np\n",
    "        if len(p) == 0 and len(s) > 0:\n",
    "            return bool(False)\n",
    "        normaled_p = ''\n",
    "        former_char = None\n",
    "        for char in p:\n",
    "            if former_char is None:\n",
    "                normaled_p+=char\n",
    "                former_char=char\n",
    "            else:\n",
    "                if former_char=='*' and char=='*':\n",
    "                    continue\n",
    "                normaled_p+=char\n",
    "                former_char=char\n",
    "        p = normaled_p\n",
    "        if len(s) == 0 and p == '*':\n",
    "            return bool(True)\n",
    "        if len(s) == 0 or len(p) == 0:\n",
    "            return len(s)==len(p)\n",
    "        records = np.zeros((len(s),len(p)))\n",
    "        def get_last_index_status(ids,idp,p_char,is_equal):\n",
    "            nonlocal records\n",
    "            if p_char=='*':\n",
    "                if idp-1<0:\n",
    "                    return True\n",
    "                else:\n",
    "                    return records[:ids+1,idp-1].max()>0\n",
    "            elif p_char=='?' or is_equal:\n",
    "                if idp-1<0:\n",
    "                    return ids == 0\n",
    "                elif ids-1<0:\n",
    "                    if idp==1 and p[0]=='*':\n",
    "                        return True\n",
    "                    return False\n",
    "                else:\n",
    "                    return records[ids-1,idp-1]>0\n",
    "            else:\n",
    "                return False\n",
    "        for ids,s_char in enumerate(s):\n",
    "            for idp,p_char in enumerate(p):\n",
    "                if get_last_index_status(ids,idp,p_char,s_char==p_char):\n",
    "                    records[ids,idp]=1\n",
    "            # print('ids:',ids,records)\n",
    "        return bool(records[len(s)-1,len(p)-1]>0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        s_len = len(s) + 1\n",
    "        p_len = len(p) + 1\n",
    "        dp = np.zeros((p_len, s_len))\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, p_len):\n",
    "            if p[i-1] == '*':\n",
    "                for j in range(0, s_len):\n",
    "                    if dp[i-1][j] == 1:\n",
    "                        dp[i][j:] = 1\n",
    "                        break\n",
    "            elif p[i-1] == '?':\n",
    "                for j in range(1, s_len):\n",
    "                    if dp[i-1][j-1] == 1:\n",
    "                        dp[i][j] = 1\n",
    "            else:\n",
    "                for j in range(1, s_len):\n",
    "                    if p[i-1] == s[j-1]:\n",
    "                        dp[i][j] = dp[i-1][j-1]\n",
    "        if dp[-1][-1] == 1:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        le_s=len(s)\n",
    "        le_p=len(p)\n",
    "        out=[[0 for u in range(le_s+1)] for v in range(le_p+1)]\n",
    "        out[0][0]=1\n",
    "        for u in range(1,le_p+1):\n",
    "            if p[u-1]==\"*\":\n",
    "                out[u][0]=out[u-1][0]\n",
    "        for p1 in range(1,le_p+1):\n",
    "            for s1 in range(1,le_s+1):\n",
    "                if p[p1-1]==s[s1-1]:\n",
    "                    out[p1][s1]=out[p1-1][s1-1]\n",
    "                elif p[p1-1]==\"?\":\n",
    "                    out[p1][s1]=out[p1-1][s1-1]\n",
    "                elif p[p1-1]==\"*\":\n",
    "                    out[p1][s1]=out[p1][s1-1]\n",
    "                    if out[p1-1][s1]  >0:\n",
    "                        out[p1][s1]=1\n",
    "        print(out)\n",
    "        return out[-1][-1]>0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        s = \"##\" + s\n",
    "        p = \"##\" + p\n",
    "        n = len(s)\n",
    "        m = len(p)\n",
    "\n",
    "        # dp = np.zeros([n, m])\n",
    "        # mx = np.zeros([n, m])\n",
    "        dp = [[False] * m for _ in range(n)]\n",
    "        mx = [[False] * m for _ in range(n)]\n",
    "        dp[0][0] = True\n",
    "        mx[0][0] = True\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, m):\n",
    "                # print(i, j)\n",
    "                if p[j] == '?' or s[i] == p[j]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                elif p[j] == '*': \n",
    "                    dp[i][j] = mx[i][j-1]\n",
    "                    # for k in range(1, i+1):\n",
    "                    #     if dp[k][j-1] == 1:\n",
    "                    #         dp[i][j] = 1\n",
    "                    #         break\n",
    "                mx[i][j] = max(mx[i-1][j], dp[i][j])\n",
    "        # print(dp)\n",
    "        return True if dp[n-1][m-1] == True else False \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        mem = {}\n",
    "        def search(m, n):\n",
    "            if n < len(p) - 1 and p[n] == '*' and p[n+1] == '*': return search(m, n+1) \n",
    "            if s[m:] == p[n:]: return True \n",
    "            if p[n:] != \"\" and p[n:].replace('*', '') == \"\": return True\n",
    "            if m >= len(s) or n >= len(p):\n",
    "                return False\n",
    "            if mem.get(m, {}).get(n) is not None:\n",
    "                return mem[m][n]\n",
    "            ans = False\n",
    "            if p[n] == '*':\n",
    "                ans = search(m, n + 1) or search(m + 1, n)\n",
    "            elif p[n] == '?' or s[m] == p[n]:\n",
    "                ans = search(m + 1, n +1)\n",
    "            else:\n",
    "                ans = False\n",
    "            if m not in mem: mem[m] = {}\n",
    "            mem[m][n] = ans\n",
    "            # print(s[m:], p[n:], ans)\n",
    "            return ans\n",
    "        return search(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        s = '#' + s + '$'\n",
    "        p = '#' + p + '$'\n",
    "        dp = [[0] * len(p) for _ in range(len(s))]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, len(s)):\n",
    "            for j in range(1, len(p)):\n",
    "                if s[i] == p[j] or p[j] == '?':\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                    if p[j-1] == '*':\n",
    "                        dp[i][j] = max(dp[i][j], dp[i][j-1])\n",
    "                elif p[j] == '*':\n",
    "                    dp[i][j] = max(dp[i - 1][j - 1], dp[i-1][j]) + 1\n",
    "                    if p[j-1] == '*':\n",
    "                        dp[i][j] = max(dp[i][j], dp[i][j-1])\n",
    "\n",
    "        # print('\\n'.join([str(t) for t in dp]))\n",
    "        # print(s, len(s))\n",
    "        return dp[-1][-1] == len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        s_len, p_len = len(s), len(p)\n",
    "        dp = [[False] * (p_len + 1) for _ in range(s_len + 1)]\n",
    "        print(dp)\n",
    "        dp[0][0] = True\n",
    "        for i in range(1, p_len+1):\n",
    "            if p[i-1] == '*':\n",
    "                dp[0][i] = True \n",
    "            else:\n",
    "                break\n",
    "                \n",
    "        for i in range(1, s_len + 1):\n",
    "            for j in range(1, p_len + 1):\n",
    "                if p[j - 1] == '*':\n",
    "                    dp[i][j] = dp[i][j - 1] | dp[i - 1][j]\n",
    "                elif p[j - 1] == '?' or s[i - 1] == p[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1]\n",
    "        return dp[s_len][p_len]\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self,s,p):\n",
    "\n",
    "        c = 0\n",
    "        for i in p:\n",
    "            if i!='*':\n",
    "                c += 1\n",
    "        if c>len(s):\n",
    "            return False\n",
    "\n",
    "        @cache\n",
    "        def matcher(hs,hp):\n",
    "            if hs==len(s) and hp==len(p):\n",
    "                return True\n",
    "            elif hs==len(s) and p[hp]=='*':\n",
    "                return matcher(hs,hp+1)\n",
    "            elif (hs==len(s)) ^ (hp==len(p)):\n",
    "                return False\n",
    "\n",
    "            if s[hs] == p[hp] or p[hp]=='?':\n",
    "                return matcher(hs+1,hp+1)\n",
    "            elif p[hp]=='*':\n",
    "                return matcher(hs+1,hp) or matcher(hs,hp+1)\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        return matcher(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        ls = len(s)\n",
    "        lp = len(p)\n",
    "        dp = [set() for _ in range(ls + 1)]\n",
    "        dp[0].add(0)\n",
    "        for i in range(lp):\n",
    "            if p[i] == '*':\n",
    "                dp[0].add(i + 1)\n",
    "            else:\n",
    "                break\n",
    "        for i in range(ls):\n",
    "            if dp[i] == set():\n",
    "                break\n",
    "            for j in list(dp[i]):\n",
    "                if j == lp:\n",
    "                    continue\n",
    "                if p[j] == '?' or p[j] == s[i]:\n",
    "                    dp[i + 1].add(j + 1)\n",
    "                elif p[j] == '*':\n",
    "                    dp[i + 1].add(j)\n",
    "                    dp[i + 1].add(j + 1)\n",
    "                else:\n",
    "                    continue\n",
    "                for k in range(j + 1, lp):\n",
    "                    if p[k] == '*':\n",
    "                        dp[i + 1].add(k + 1)\n",
    "                    else:\n",
    "                        break\n",
    "        \n",
    "        print(dp)\n",
    "        return lp in dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        lp,ls = len(p),len(s)\n",
    "        dp = [set() for _ in range(lp+1)]\n",
    "        dp[0].add(-1)\n",
    "        for i in range(lp):\n",
    "            if p[i] == '?':\n",
    "                for x in dp[i]:\n",
    "                    if x + 1 < ls:\n",
    "                        dp[i+1].add(x+1)\n",
    "            elif p[i] == '*':\n",
    "                minx = ls\n",
    "                for x in dp[i]: minx = min(minx, x)\n",
    "                while minx < ls:\n",
    "                    dp[i+1].add(minx)\n",
    "                    minx += 1\n",
    "            else:\n",
    "                for x in dp[i]:\n",
    "                    if x+1 < ls and s[x+1] == p[i]:\n",
    "                        dp[i+1].add(x+1)\n",
    "        if ls-1 in dp[-1]:\n",
    "            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        dp = [set() for _ in range(len(p)+1)]\n",
    "        dp[0].add(-1)\n",
    "        for i in range(len(p)):\n",
    "            if p[i] == '?':\n",
    "                for x in dp[i]:\n",
    "                    if x + 1 < len(s):\n",
    "                        dp[i+1].add(x+1)\n",
    "            elif p[i] == '*':\n",
    "                minx = len(s)\n",
    "                for x in dp[i]: minx = min(minx, x)\n",
    "                while minx < len(s):\n",
    "                    dp[i+1].add(minx)\n",
    "                    minx += 1\n",
    "            else:\n",
    "                for x in dp[i]:\n",
    "                    if x+1 < len(s) and s[x+1] == p[i]:\n",
    "                        dp[i+1].add(x+1)\n",
    "        if len(s)-1 in dp[-1]:\n",
    "            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    cache_result = {}\n",
    "\n",
    "    def merge_star(self, p: str):\n",
    "        while \"**\" in p:\n",
    "            p = p.replace(\"**\", \"*\")\n",
    "        return p\n",
    "\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        p = self.merge_star(p)\n",
    "\n",
    "        if (s, p) in self.cache_result:\n",
    "            return self.cache_result[(s, p)]\n",
    "\n",
    "        slen = len(s)\n",
    "        plen = len(p)\n",
    "\n",
    "        si = 0\n",
    "        pi = 0\n",
    "\n",
    "        while pi < plen:\n",
    "            pval = p[pi]\n",
    "            sval = s[si] if si < slen else None\n",
    "            if pval == \"?\":\n",
    "                # 跳过, 匹配任何单个字符\n",
    "                pass\n",
    "            elif pval == \"*\":\n",
    "                # 星号, 可以匹配任意数量的任意字符\n",
    "                # 所以就把任意的可能性都去尝试一遍\n",
    "                result = any(self.isMatch(s[x:], p[pi+1:]) for x in range(si, slen+1))\n",
    "                self.cache_result[(s, p)] = result\n",
    "                return result\n",
    "            else:\n",
    "                if pval != sval:\n",
    "                    self.cache_result[(s, p)] = False\n",
    "                    return False\n",
    "            \n",
    "            si += 1\n",
    "            pi += 1\n",
    "        \n",
    "        # 只有一起到达终点, 才算是匹配成功\n",
    "        if si == slen and pi == plen:\n",
    "            self.cache_result[(s, p)] = True\n",
    "            return True\n",
    "        self.cache_result[(s, p)] = False\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        self.s = s+'$'\n",
    "        self.p = re.sub(r\"\\*+\", \"*\", p) + '$'\n",
    "        # return bool(re.fullmatch(self.p.replace(\"*\", \"[a-z]*\").replace(\"?\", \".\"), s))\n",
    "        \n",
    "        self.cache = dict()\n",
    "        return self.m(0,0)\n",
    "\n",
    "    def m2(self, si, pi):\n",
    "        if (si*2000 + pi) in self.cache:\n",
    "            return self.cache[si*2000 + pi]\n",
    "        \n",
    "        r = self.m(si, pi)\n",
    "        self.cache[si*2000 + pi] = r\n",
    "        return r\n",
    "\n",
    "\n",
    "    def m(self,si, pi):\n",
    "        if si==len(self.s) and pi==len(self.p):\n",
    "            return True\n",
    "        if si>=len(self.s) or pi>=len(self.p):\n",
    "            return False\n",
    "\n",
    "        if self.p[pi] == '?':\n",
    "            return self.m2( si+1, pi+1)\n",
    "        elif self.p[pi] == '*':\n",
    "            return self.m2( si+1, pi) or self.m2( si, pi+1)\n",
    "        else:\n",
    "            if self.s[si]!=self.p[pi]:\n",
    "                return False\n",
    "            else:\n",
    "                return self.m2( si+1, pi+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        p = re.sub(r\"\\*+\", \"*\", p)\n",
    "        # return bool(re.fullmatch(p.replace(\"*\", \"[a-z]*\").replace(\"?\", \".\"), s))\n",
    "        \n",
    "        self.cache = dict()\n",
    "        return self.m(s+'$',p+'$',0,0)\n",
    "\n",
    "    def m2(self, s,p,si, pi):\n",
    "        if (si*2000 + pi) in self.cache:\n",
    "            return self.cache[si*2000 + pi]\n",
    "        \n",
    "        r = self.m(s,p,si, pi)\n",
    "        self.cache[si*2000 + pi] = r\n",
    "        return r\n",
    "\n",
    "\n",
    "    def m(self, s,p,si, pi):\n",
    "        if si==len(s) and pi==len(p):\n",
    "            return True\n",
    "        if si>=len(s) or pi>=len(p):\n",
    "            return False\n",
    "\n",
    "        if p[pi] == '?':\n",
    "            return self.m2(s, p, si+1, pi+1)\n",
    "        elif p[pi] == '*':\n",
    "            return self.m2(s, p, si+1, pi) or self.m2(s, p, si, pi+1)\n",
    "        else:\n",
    "            if s[si]!=p[pi]:\n",
    "                return False\n",
    "            else:\n",
    "                return self.m2(s, p, si+1, pi+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        automaton = {}\n",
    "        state = 0\n",
    "\n",
    "        for i in range(len(p)):\n",
    "            if p[i] == '?':\n",
    "                automaton[state] = { '?' : state + 1 }\n",
    "            elif p[i] == '*':\n",
    "                automaton[state] = { '*' : state + 1 }\n",
    "            else:\n",
    "                automaton[state] = { p[i] : state + 1 }\n",
    "            state = state + 1\n",
    "\n",
    "        end_state = state\n",
    "        automaton[end_state] = {}\n",
    "\n",
    "        dp = {}\n",
    "        def innerIsMatch(i, state):\n",
    "            j = i\n",
    "\n",
    "            if dp.get((i, state)) != None:\n",
    "                return dp[(i, state)]\n",
    "\n",
    "            while j < len(s):\n",
    "                ch = s[j]\n",
    "                # The character is in the transition table\n",
    "                if automaton[state].get(ch) != None:\n",
    "                    j = j + 1\n",
    "                    state = state + 1\n",
    "                # The character is not in the transition table but a '?' is available\n",
    "                elif automaton[state].get('?') != None:\n",
    "                    j = j + 1\n",
    "                    state = state + 1\n",
    "                # The character is not in the transition table but a '*' is available\n",
    "                elif automaton[state].get('*') != None:\n",
    "                    # Choose to match '*' with the current character and consider it a full match\n",
    "                    transition = innerIsMatch(j + 1, state + 1)\n",
    "                    dp[(j + 1, state + 1)] = transition\n",
    "                    # Choose to match '*' with the current character and consider it a partial match\n",
    "                    repeat = innerIsMatch(j + 1, state)\n",
    "                    dp[(j + 1, state)] = repeat\n",
    "                    # Choose to not match '*' with the current character (i.e. match '*' with an empty string)\n",
    "                    skip = innerIsMatch(j, state + 1)\n",
    "                    dp[(j, state + 1)] = skip\n",
    "                    return repeat or transition or skip\n",
    "                else:\n",
    "                    return False\n",
    "            \n",
    "            if j >= len(s):\n",
    "                while automaton[state].get('*') != None:\n",
    "                    state = state + 1\n",
    "            \n",
    "            if state == end_state:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        \n",
    "        return innerIsMatch(0, 0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        m = len(s)\n",
    "        n = len(p)\n",
    "        memo = {}\n",
    "\n",
    "        def isMatch(i: int, j: int):\n",
    "            # base cases\n",
    "            if j == n:\n",
    "                return i == m\n",
    "            if i == m:\n",
    "                for j in range(j, n):\n",
    "                    if p[j] == '*':\n",
    "                        continue\n",
    "                    else:\n",
    "                        return False\n",
    "                return True\n",
    "\n",
    "            # check repeated\n",
    "            key = str(i) + ',' + str(j)\n",
    "            if key in memo:\n",
    "                return memo[key]\n",
    "\n",
    "            res = False\n",
    "            if p[j] == '*':\n",
    "                while j < n and p[j] == '*':\n",
    "                    j += 1\n",
    "                for i in range(i, m + 1):\n",
    "                    res |= isMatch(i, j)\n",
    "                    if res: \n",
    "                        break\n",
    "            else:\n",
    "                if s[i] == p[j] or p[j] == '?':\n",
    "                    res = isMatch(i + 1, j + 1)\n",
    "                else:\n",
    "                    res = False\n",
    "            \n",
    "            memo[key] = res\n",
    "            return res\n",
    "        \n",
    "        return isMatch(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        memo = {}\n",
    "        m, n = len(s), len(p)\n",
    "        if not n : return not m\n",
    "        if not m :\n",
    "            for i in range(n) :\n",
    "                if p[i] != '*' :\n",
    "                    return False\n",
    "            return True\n",
    "        return self.dp(memo, s, 0, p, 0)\n",
    "    \n",
    "    def dp(self,memo: map, s: str, i: int, p: str, j: int) -> bool :\n",
    "        m, n = len(s), len(p)\n",
    "        if j == n : return i == m\n",
    "        if i == m :\n",
    "            for k in range(j, n) :\n",
    "                if p[k] != '*' : \n",
    "                    return False\n",
    "            return True\n",
    "        key = str(i) + ',' + str(j)\n",
    "        x = memo.get(key, -1)\n",
    "        if x != -1 :\n",
    "            return memo[key]\n",
    "        res = False\n",
    "        if i >= m or j >= n :\n",
    "            return False\n",
    "        if s[i] == p[j] or p[j] == '?':\n",
    "            res = self.dp(memo, s, i+1, p, j+1)\n",
    "        elif p[j] == '*' :\n",
    "            res = self.dp(memo, s, i+1, p, j) or self.dp(memo, s, i, p, j+1) or self.dp(memo, s, i+1, p, j+1)\n",
    "        else :\n",
    "            res = False\n",
    "\n",
    "        memo[key] = res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        def isMatchInner(s: str, p: str, si: int, pi: int, memo: Dict[str, bool]) -> bool:\n",
    "            key = f'{si}|{pi}'\n",
    "            if key in memo:\n",
    "                return memo[key]\n",
    "            else:\n",
    "                if si >= len(s) and pi >= len(p):\n",
    "                    return True\n",
    "                elif pi >= len(p):\n",
    "                    return False\n",
    "                else:\n",
    "                    px = p[pi]\n",
    "                    if px == '?':\n",
    "                        if si >= len(s):\n",
    "                            memo[key] = False\n",
    "                            return False\n",
    "                        else:\n",
    "                            result = isMatchInner(s, p, si + 1, pi + 1, memo)\n",
    "                            memo[key] = result\n",
    "                            return result\n",
    "                    elif px == '*':\n",
    "                        for l in range(1 + len(s) - si):\n",
    "                            if isMatchInner(s, p, si + l, pi + 1, memo):\n",
    "                                memo[key] = True\n",
    "                                return True\n",
    "                        memo[key] = False\n",
    "                        return False\n",
    "                    else: # px != '?' and px != '*':\n",
    "                        if si == len(s) or s[si] != px:\n",
    "                            return False\n",
    "                        result = isMatchInner(s, p, si + 1, pi + 1, memo)\n",
    "                        memo[key] = result\n",
    "                        return result\n",
    "        return isMatchInner(s, p, 0, 0, {})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        memo = {}\n",
    "        def dp(s,p,i,j):\n",
    "            m = len(s)\n",
    "            n = len(p)\n",
    "            if j == n:\n",
    "                return i == m\n",
    "            if i == m:\n",
    "                while j < n:\n",
    "                    if p[j] != '*':\n",
    "                        return False\n",
    "                    j += 1\n",
    "                return True\n",
    "            key = str(i)+','+str(j)\n",
    "            if key in memo:\n",
    "                return memo[key]\n",
    "            res = False\n",
    "            if s[i] == p[j] or p[j] == '?':\n",
    "                res = dp(s,p,i+1,j+1)\n",
    "            else:\n",
    "                if p[j] == '*':\n",
    "                    res = (dp(s,p,i+1,j) or dp(s,p,i,j+1))\n",
    "                else:\n",
    "                    res =  False\n",
    "            memo[key] = res \n",
    "            return res\n",
    "        return dp(s,p,0,0)\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        dp_dict = {}\n",
    "        def dp(s, i, p, j):\n",
    "            if j == len(p):\n",
    "                return i == len(s)\n",
    "            if i == len(s):\n",
    "                for m in range(j, len(p)):\n",
    "                    if p[m] != '*':\n",
    "                        return False\n",
    "                return True\n",
    "            key = str(i) + ',' + str(j)\n",
    "            if key in dp_dict.keys():\n",
    "                return dp_dict[key]\n",
    "            res = False\n",
    "            if s[i] == p[j] or p[j] == '?':\n",
    "                res = dp(s, i+1, p, j+1)\n",
    "            if p[j] != '?' and p[j] != '*' and s[i] != p[j]:\n",
    "                res = False\n",
    "            if p[j] == '*':\n",
    "                if j == len(p)-1: # p中的*匹配s中的剩余所有字符\n",
    "                    res = True\n",
    "                elif p[j+1] == '?':  # *后面跟着一个?的话*匹配任意个字符\n",
    "                    tmp = False  # 从0个开始\n",
    "                    for m in range(i, len(s)):\n",
    "                        tmp = tmp or dp(s, m, p, j+1)\n",
    "                    res = tmp\n",
    "                elif p[j+1] == '*':\n",
    "                    res = dp(s, i, p, j+1)\n",
    "                else:\n",
    "                    alpha = p[j+1]\n",
    "                    alpha_index = []\n",
    "                    for m in range(i, len(s)):\n",
    "                        if s[m] == alpha:\n",
    "                            alpha_index.append(m)\n",
    "                    tmp = False\n",
    "                    for index in alpha_index:\n",
    "                        tmp = tmp or dp(s, index, p, j+1)\n",
    "                    res = tmp\n",
    "            dp_dict[key] = res\n",
    "            return res\n",
    "        return dp(s, 0, p, 0)\n",
    "                    \n",
    "\n",
    "                \n",
    "             \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        m, n = len(s), len(p)\n",
    "        memo = {}\n",
    "        def dp(s,i,p,j):\n",
    "            if j == n: return i == m\n",
    "            if i == m:\n",
    "                for k in range(j, n):\n",
    "                    if p[k] != '*': return False\n",
    "                return True\n",
    "\n",
    "            key = str(i)+','+str(j)\n",
    "            if key in memo: return memo[key]\n",
    "            res = False\n",
    "\n",
    "            if s[i] == p[j] or p[j] =='?':\n",
    "                res = dp(s,i+1,p,j+1)\n",
    "            elif p[j] =='*':\n",
    "                res = dp(s,i,p,j+1) or dp(s,i+1,p,j)\n",
    "            else:\n",
    "                res = False\n",
    "            memo[key] = res\n",
    "            return res\n",
    "        return dp(s,0,p,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        dp = defaultdict(lambda: defaultdict(bool))\n",
    "        dp[-1][-1] = True\n",
    "        for j in range(len(p)):\n",
    "            dp[-1][j] = p[:j].replace('*', '') == '' and p[j] == '*'\n",
    "        for i, char in enumerate(s):\n",
    "            for j, pattern in enumerate(p):\n",
    "                if pattern == '*':\n",
    "                    dp[i][j] = dp[i - 1][j] or dp[i][j - 1]\n",
    "                elif pattern == '?' or pattern == char:\n",
    "                    dp[i][j] = dp[i - 1][j - 1]\n",
    "                elif pattern != char:\n",
    "                    dp[i][j] = False\n",
    "        return dp[len(s) - 1][len(p) - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        n = len(s)\n",
    "        m = len(p)\n",
    "        @lru_cache(10000)\n",
    "        def dfs(i,j):\n",
    "            if i== n and j == m:\n",
    "                return True  \n",
    "            if i<n and j<m and (s[i] == p[j] or p[j] == '?'):\n",
    "                return dfs(i+1,j+1)\n",
    "            elif j<m and p[j] == '*':\n",
    "                if i==n:\n",
    "                    return dfs(i,j+1)\n",
    "                return dfs(i+1,j) or dfs(i,j+1)\n",
    "            else:\n",
    "                return False\n",
    "        return dfs(0,0)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#思路：有限状态自动机 + 宽度优先搜索（也可以用深度优先搜索）\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        \n",
    "        #边界情况的处理\n",
    "        if p == '':\n",
    "            if s == '':\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "            \n",
    "        elif len(p) == 1:\n",
    "            if p == '*':\n",
    "                return True\n",
    "            elif p == '?' and len(s) == 1:\n",
    "                return True\n",
    "            elif p == s:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        elif s == '':\n",
    "            if p == '' or set(p) == {'*'}:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "            \n",
    "        #一般情况\n",
    "        else:\n",
    "            \n",
    "            #从p构建NFA\n",
    "            alphabet = set(s)\n",
    "            trans = dict()\n",
    "            trans[0] = dict()\n",
    "            state = 0\n",
    "            for i in range(len(p)):\n",
    "                if p[i] == '*':\n",
    "                    for c in alphabet:\n",
    "                        trans[state][c] = {state}\n",
    "                elif p[i] == '?':\n",
    "                    for c in alphabet:\n",
    "                        if c not in trans[state]: #对应前一个模式符是?或字母的情况\n",
    "                            trans[state][c] = {state + 1}\n",
    "                        else: #对应前一个模式符是*的情况\n",
    "                            trans[state][c].add(state + 1)\n",
    "                    state += 1\n",
    "                    trans[state] = dict()\n",
    "                else:\n",
    "                    if p[i] not in trans[state]: #对应前一个模式符是?或字母的情况\n",
    "                        trans[state][p[i]] = {state + 1}\n",
    "                    else: #对应前一个模式符是*的情况\n",
    "                        trans[state][p[i]].add(state + 1)\n",
    "                    state += 1\n",
    "                    trans[state] = dict()\n",
    "                \n",
    "            start = 0\n",
    "            accept = state\n",
    "\n",
    "##            #检查NFA生成得正不正确\n",
    "##            for t in trans:\n",
    "##                print(t, trans[t])\n",
    "                \n",
    "            #用宽度优先搜索对s进行匹配\n",
    "            from collections import deque\n",
    "            visited = set()\n",
    "            toBeExpanded = deque([(0, 0)])\n",
    "            while toBeExpanded:\n",
    "                state, i = toBeExpanded.popleft()\n",
    "                if (state, i) not in visited:\n",
    "                    if i < len(s) and s[i] in trans[state]:\n",
    "                        for nextState in trans[state][s[i]]:\n",
    "                            if nextState == accept and i == len(s) - 1:\n",
    "                                return True\n",
    "                            else:\n",
    "                                toBeExpanded.append((nextState, i + 1))\n",
    "                    visited.add((state, i))\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        '''\n",
    "        与第10题类似，但有所不同\n",
    "        直接递归只通过了1760 / 1809个测试样例，\n",
    "        需要优化一下，想想办法剪个枝\n",
    "        加了第一个剪枝之后，通过了1747 / 1809 个样例\n",
    "        加了第二个剪枝条件之后，通过了1805 / 1809个样例，还差最后4个样例没有通过\n",
    "        '''\n",
    "        #1. 递归边界条件 \n",
    "        if s==p:\n",
    "            # 都为空，或者相同\n",
    "            return True \n",
    "        if len(p)==0:\n",
    "            # 空字符模式 无法匹配 非空字符串\n",
    "            return False \n",
    "        # 2. 剪枝： p中除*外的字符数量应该不超过s的长度，\n",
    "        if 2>1:\n",
    "            ll = len(s)\n",
    "            t = False \n",
    "            for c in p:\n",
    "                if c!='*':\n",
    "                    ll -= 1\n",
    "                else:\n",
    "                    t = True \n",
    "            if ll<0 or (ll>0 and not t):\n",
    "                return False \n",
    "        # 每个字母的数量应该都不超过s中的数量\n",
    "        # 对p的字符进行便利\n",
    "        c = p[0]\n",
    "        if c=='*':\n",
    "            # 如果p的开头有多个*，则全部删除掉\n",
    "            j = 1 \n",
    "            if 3>1:\n",
    "                # 第二次剪枝\n",
    "                while j<len(p) and p[j]=='*':\n",
    "                    j += 1\n",
    "            for i in range(len(s)+1):\n",
    "                if self.isMatch(s[i:], p[j:]):\n",
    "                    return True \n",
    "            else:\n",
    "                return False \n",
    "        elif len(s)==0:\n",
    "            return False\n",
    "        elif c=='?':\n",
    "            return self.isMatch(s[1:], p[1:]) \n",
    "        elif c==s[0]:\n",
    "            return self.isMatch(s[1:], p[1:])\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        def buildEdges():\n",
    "            statusId = 0\n",
    "            edges = defaultdict(list)\n",
    "            for patternCh in p:\n",
    "                if patternCh != '*':\n",
    "                    edges[statusId].append((patternCh, statusId + 1))\n",
    "                    statusId += 1\n",
    "                else:\n",
    "                    edges[statusId].append(('', statusId + 1))\n",
    "                    edges[statusId + 1].append(('?', statusId + 1))\n",
    "                    statusId += 1\n",
    "            endStatusId = statusId\n",
    "            return edges, endStatusId\n",
    "\n",
    "        @lru_cache(maxsize=None)\n",
    "        def dfs(status: int, stringI: int) -> bool:\n",
    "            if endStatusId == status:\n",
    "                return stringI == len(s)\n",
    "            if stringI == len(s):\n",
    "                return edges[status][-1][0] == ('#', endStatusId)\n",
    "            for edgeChar, toStatusId in edges[status]:\n",
    "                if edgeChar == '?' or edgeChar == s[stringI]:  # 匹配一个字符\n",
    "                    if dfs(toStatusId, stringI + 1):\n",
    "                        return True\n",
    "                elif edgeChar == '':  # epsilon\n",
    "                    if dfs(toStatusId, stringI):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        s += '#'\n",
    "        p += '#'\n",
    "        edges, endStatusId = buildEdges()\n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        newp='a'\n",
    "        for i in range(len(p)):\n",
    "            if newp[-1]=='*' and p[i]=='*':\n",
    "                continue\n",
    "            else:\n",
    "                newp=newp+p[i]\n",
    "        newpp=newp[1:]\n",
    "        memory={}\n",
    "\n",
    "        def aaaa(ssub,psub):\n",
    "            if (ssub,psub) in memory.keys():\n",
    "                return memory[(ssub,psub)]\n",
    "\n",
    "            if len(psub)==0 and len(ssub)==0:\n",
    "                return True\n",
    "            elif len(psub)!=0 and len(ssub)==0:\n",
    "                for i in range(len(psub)):\n",
    "                    if psub[i]!='*':\n",
    "                        return False\n",
    "                return True\n",
    "            elif len(psub)==0 and len(ssub)!=0:\n",
    "                return False\n",
    "            sstart=0\n",
    "            pstart=0\n",
    "            while sstart<len(ssub) and pstart<len(psub) :\n",
    "                if ssub[sstart]!=psub[pstart] :\n",
    "                    if psub[pstart]=='?':\n",
    "                        memory[(ssub[sstart+1:],psub[pstart+1:])]=aaaa(ssub[sstart+1:],psub[pstart+1:])\n",
    "                        return memory[(ssub[sstart+1:],psub[pstart+1:])]\n",
    "                    elif psub[pstart]=='*': \n",
    "                        memory[(ssub[sstart+1:],psub[pstart:])]=aaaa(ssub[sstart+1:],psub[pstart:])\n",
    "                        memory[(ssub[sstart+1:],psub[pstart+1:])]=aaaa(ssub[sstart+1:],psub[pstart+1:])\n",
    "                        memory[(ssub[sstart:],psub[pstart+1:])]=aaaa(ssub[sstart:],psub[pstart+1:])\n",
    "                        return  memory[(ssub[sstart+1:],psub[pstart:])] or memory[(ssub[sstart+1:],psub[pstart+1:])] or memory[(ssub[sstart:],psub[pstart+1:])]\n",
    "                    else :\n",
    "                        memory[(ssub,psub)]=False\n",
    "                        return False\n",
    "                sstart+=1\n",
    "                pstart+=1     \n",
    "            memory[(ssub[sstart:],psub[pstart:])]=aaaa(ssub[sstart:],psub[pstart:])     \n",
    "            return memory[(ssub[sstart:],psub[pstart:])]\n",
    "        return aaaa(s,newpp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        return self.DP(s, p)\n",
    "\n",
    "    # 回溯\n",
    "    def BT(self, s: str, p: str) -> bool:\n",
    "        pass\n",
    "\n",
    "    # 动态规划 两个维度 (len(s), len(p))\n",
    "    def DP(self, s: str, p: str) -> bool:\n",
    "        if len(s) == 0:\n",
    "            if p == \"*\" or len(p) == 0:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        if len(p) == 0:\n",
    "            return False\n",
    "        # (len(s)与len(p)是否匹配，len(p)与len(0-s)是否匹配)\n",
    "        matrix: [[(bool, bool)]] = [[(False, False)] * (len(p) + 1) for _ in range(len(s) + 1)]\n",
    "        matrix[0][0] = (True, False)\n",
    "\n",
    "        for ii_p, c_p in enumerate(p):\n",
    "            i_p = ii_p + 1\n",
    "            if c_p == '*':\n",
    "                matrix[0][i_p] = (True, True)\n",
    "            else:\n",
    "                break\n",
    "        for ii_s, c_s in enumerate(s):\n",
    "            for ii_p, c_p in enumerate(p):\n",
    "                i_s = ii_s + 1\n",
    "                i_p = ii_p + 1\n",
    "                if 'a' <= c_p <= 'z':\n",
    "                    # print(matrix[i_s - 1][i_p - 1])\n",
    "                    r = (matrix[i_s - 1][i_p - 1][0]) and (c_p == c_s)\n",
    "                    matrix[i_s][i_p] = (r, r or matrix[i_s - 1][i_p][1])\n",
    "\n",
    "                elif c_p == '?':\n",
    "                    matrix[i_s][i_p] = (\n",
    "                    matrix[i_s - 1][i_p - 1][0], matrix[i_s - 1][i_p - 1][0] or matrix[i_s - 1][i_p][1])\n",
    "                else:\n",
    "                    if matrix[i_s][i_p - 1][1] or i_p == 1:\n",
    "                        matrix[i_s][i_p] = (True, True)\n",
    "                    else:\n",
    "                        matrix[i_s][i_p] = (False, matrix[i_s - 1][i_p][1])\n",
    "        # for l in matrix:\n",
    "        #     print(l)\n",
    "        return matrix[len(s)][len(p)][0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def add_states(self,content):\n",
    "        if content not in self.ban:\n",
    "            self.states.append(content)\n",
    "            self.ban.add(content)\n",
    "            # print(len(self.states))\n",
    "\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        self.ban=set()\n",
    "        self.states=[(0,0)]\n",
    "        ban = set()\n",
    "        while self.states:\n",
    "            sp,pp=self.states.pop()\n",
    "            if pp==len(p):\n",
    "                if sp>=len(s):\n",
    "                    return True \n",
    "            else:\n",
    "                if p[pp]=='*':\n",
    "                    self.add_states((sp,pp+1))\n",
    "                    if sp<len(s):\n",
    "                        self.add_states((sp+1,pp))\n",
    "                        self.add_states((sp+1,pp+1))\n",
    "                elif p[pp]=='?': \n",
    "                    if sp<len(s):\n",
    "                        self.add_states((sp+1,pp+1))\n",
    "                else:\n",
    "                    if sp<len(s) and p[pp]==s[sp]  :\n",
    "                        self.add_states((sp+1,pp+1))\n",
    "        return False\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def add_states(self,content):\n",
    "        if content not in self.ban:\n",
    "            self.states.append(content)\n",
    "            self.ban.add(content)\n",
    "            print(len(self.states))\n",
    "\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        self.ban=set()\n",
    "        self.states=[(0,0)]\n",
    "        ban = set()\n",
    "        while self.states:\n",
    "            sp,pp=self.states.pop()\n",
    "            if pp==len(p):\n",
    "                if sp>=len(s):\n",
    "                    return True \n",
    "            else:\n",
    "                if p[pp]=='*':\n",
    "                    self.add_states((sp,pp+1))\n",
    "                    if sp<len(s):\n",
    "                        self.add_states((sp+1,pp))\n",
    "                        self.add_states((sp+1,pp+1))\n",
    "                elif p[pp]=='?': \n",
    "                    if sp<len(s):\n",
    "                        self.add_states((sp+1,pp+1))\n",
    "                else:\n",
    "                    if sp<len(s) and p[pp]==s[sp]  :\n",
    "                        self.add_states((sp+1,pp+1))\n",
    "        return False\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self) -> None:\n",
    "        self.cache = set()\n",
    "\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        m, n = len(s), len(p)\n",
    "        if m == 0:\n",
    "            if n == 0:\n",
    "                return True\n",
    "            elif p[n - 1] == '*':\n",
    "                return self.isMatch(s, p[:n - 1])\n",
    "            else:\n",
    "                return False\n",
    "        elif n == 0:\n",
    "            return False\n",
    "        if (m, n) in self.cache:\n",
    "            return False\n",
    "        self.cache.add((m, n))\n",
    "        if p[n - 1] == '?' or s[m - 1] == p[n - 1]:\n",
    "            return self.isMatch(s[:m - 1], p[:n - 1])\n",
    "        elif p[n - 1] == '*':\n",
    "            return self.isMatch(s[:m], p[:n - 1]) or self.isMatch(s[:m - 1], p[:n])\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:        \n",
    "        return self.helper(s, 0, p, 0, {})\n",
    "\n",
    "    def helper(self, s, i, p, j, memo):\n",
    "        # 从i，j开始，后面字符串能否匹配\n",
    "        # 1.s,p恰好匹配完\n",
    "        if j == len(p):\n",
    "            return i == len(s)\n",
    "        # 2.s匹配完，p必须只剩*\n",
    "        if i == len(s):\n",
    "            return self.all_star(p, j)\n",
    "        if (i, j) in memo:\n",
    "            return memo[(i, j)]\n",
    "        \n",
    "        if p[j] != \"*\":\n",
    "            match = self.char_match(s, i, p, j) and self.helper(s, i + 1, p, j + 1, memo)\n",
    "        else:\n",
    "            match =  self.helper(s, i, p, j + 1, memo) or self.helper(s, i + 1, p, j, memo)\n",
    "        memo[(i, j)] = match\n",
    "        return match\n",
    "\n",
    "    def all_star(self, p, j):\n",
    "        for i in range(j, len(p)):\n",
    "            if p[i] != \"*\":\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "    def char_match(self, s, i, p, j):\n",
    "        return s[i] == p[j] or p[j] == '?'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        sn, pn = len(s), len(p)\n",
    "        @cache\n",
    "        def dfs(si, pi):\n",
    "            if pi    == pn : return si == sn\n",
    "            if p[pi] == '?': return si < sn and dfs(si + 1, pi + 1)\n",
    "            if p[pi] == '*': return any(dfs(si_, pi + 1) for si_ in range(si, sn + 1))\n",
    "            return si < sn and s[si] == p[pi] and dfs(si + 1, pi + 1)\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def __init__(self):\n",
    "        self.cache = {}\n",
    "\n",
    "    def prepare(self, pattern):\n",
    "        op = ''\n",
    "        while op != pattern:\n",
    "            op = pattern\n",
    "            pattern = pattern.replace('**', '*')\n",
    "        return op\n",
    "\n",
    "    def isMatch(self, s, p):\n",
    "        np = self.prepare(p)\n",
    "        self.s = s\n",
    "        self.p = np\n",
    "        return self._isMatch()\n",
    "    \n",
    "    def _isMatch(self, si=0, pi=0):\n",
    "        if (si, pi) in self.cache:\n",
    "            return self.cache[(si, pi)]\n",
    "        pp = self.p[pi:].strip('*')\n",
    "        if si == len(self.s) and len(pp) == 0:\n",
    "            return True\n",
    "        if pi == len(self.p):  # 且s没有匹配完\n",
    "            return False\n",
    "        if si == len(self.s) and len(pp) != 0:\n",
    "            return False\n",
    "        ns, np = self.s[si], self.p[pi]\n",
    "        if (np == '?'):\n",
    "            self.cache[(si, pi)] = self._isMatch(si+1, pi+1)\n",
    "            return self.cache[(si, pi)]\n",
    "        if (np == '*'):\n",
    "            self.cache[(si, pi)] = self._isMatch(si, pi+1) or self._isMatch(si+1, pi)\n",
    "            return self.cache[(si, pi)]\n",
    "        if (np == ns):\n",
    "            self.cache[(si, pi)] = self._isMatch(si+1, pi+1)\n",
    "            return self.cache[(si, pi)]\n",
    "        self.cache[(si, pi)] = False\n",
    "        return self.cache[(si, pi)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        if s==\"\" and p.count('*')==len(p):\n",
    "            return True\n",
    "        if s==\"\" or p ==\"\":\n",
    "            return False\n",
    "\n",
    "        sindex = 0\n",
    "        ans = False\n",
    "        i=0\n",
    "        while i<=len(p) and sindex<=len(s):\n",
    "\n",
    "            if sindex==len(s):\n",
    "                if p[i:].count(\"*\")==len(p[i:]):\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "            if i == len(p):\n",
    "                if sindex<len(s):\n",
    "                    return False\n",
    "                else:\n",
    "                    return True\n",
    "\n",
    "            if s[sindex]==p[i]:\n",
    "                sindex+=1\n",
    "            elif p[i]==\"?\":\n",
    "                sindex+=1\n",
    "            elif p[i] == \"*\":\n",
    "                #可以仅匹配当前\n",
    "                #可以不匹配\n",
    "                #可以匹配多个\n",
    "                #0-n\n",
    "                nextIndex = sindex\n",
    "                while nextIndex<=len(s):\n",
    "                    ans = ans or self.isMatch(s[nextIndex:],p[i+1:])\n",
    "                    nextIndex+=1\n",
    "\n",
    "                    if ans:\n",
    "                        break\n",
    "                return ans\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "            i+=1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        if len(s) == len(p) == 0: return True\n",
    "        if len(s) == 0 and set(p)=={'*'}: return True\n",
    "        if len(s)*len(p) == 0: return False\n",
    "        j = 0\n",
    "        for i in range(len(s)):\n",
    "            if j==len(p): return False\n",
    "            if p[j]=='*': return any(self.isMatch(s[k:], p[j+1:]) for k in range(i, len(s)+1))\n",
    "            elif p[j] == '?' or s[i]==p[j]: j+=1\n",
    "            else: return False\n",
    "        return (j == len(p)) or set(p[j:])=={'*'}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        @lru_cache(None)\n",
    "        def dfs(si, pi):\n",
    "            if pi == n:\n",
    "                return si == m\n",
    "            if p[pi] != '*':\n",
    "                return si != m and (s[si] == p[pi] or p[pi] == '?') and dfs(si + 1, pi + 1)\n",
    "            else:\n",
    "                while pi + 1 < n and p[pi + 1] == '*':\n",
    "                    pi += 1\n",
    "                while si <= m:\n",
    "                    if dfs(si, pi + 1):\n",
    "                        return True\n",
    "                    si += 1\n",
    "            return False\n",
    "        m, n = len(s), len(p)\n",
    "        return dfs(0, 0)\n",
    "\n",
    "\n",
    "\n",
    "        # @lru_cache(None)\n",
    "        # def dfs(si, pi):\n",
    "        #     # print(si, pi)\n",
    "        #     if pi == n:\n",
    "        #         return si == m \n",
    "        #     if p[pi] != '*':\n",
    "        #         return si != m and (s[si] == p[pi] or p[pi] == '?') and dfs(si + 1, pi + 1)\n",
    "        #     else:\n",
    "        #         while pi + 1 < n and p[pi + 1] == '*':\n",
    "        #             pi += 1\n",
    "        #         if pi + 1 == n:\n",
    "        #             return True\n",
    "        #         while si + 1 < m and s[si + 1] != p[pi + 1]:\n",
    "        #             si += 1\n",
    "        #         if si + 1 == m:\n",
    "        #             return False\n",
    "        #         return dfs(si + 2, pi + 2)\n",
    "\n",
    "        # m, n = len(s), len(p)\n",
    "        # return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        if len(p) == 0:\n",
    "            return len(s) == 0\n",
    "        else:\n",
    "            sp = p[0]\n",
    "            for i in range(1, len(p)):\n",
    "                if p[i] == '*' and p[i] == p[i-1]:\n",
    "                    continue\n",
    "                else:\n",
    "                    sp += p[i]\n",
    "        \n",
    "        m = len(s)\n",
    "        n = len(sp)\n",
    "        @cache\n",
    "        def check(i,j)->bool:\n",
    "            if i==m and j==n:\n",
    "                return True\n",
    "            elif i<m and j==n:\n",
    "                return False\n",
    "            elif i==m and j<n:\n",
    "                if n-j>1:\n",
    "                    return False\n",
    "                elif sp[j]=='*':\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if sp[j]=='?':\n",
    "                    return check(i+1, j+1)\n",
    "                elif sp[j]=='*':\n",
    "                    for ii in range(i, m+1):\n",
    "                        if check(ii, j+1):\n",
    "                            return True\n",
    "                    return False\n",
    "                else:\n",
    "                    return check(i+1, j+1) if sp[j]==s[i] else False\n",
    "\n",
    "        return check(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        sl = len(s)\n",
    "        pl = len(p)\n",
    "        @cache\n",
    "        def isMatch(s, p, sf, pf):\n",
    "            if sf == sl and pf == pl:\n",
    "                return True\n",
    "            if pf < pl and p[pf] == '*':\n",
    "                return max([isMatch(s, p, sf + i, pf + 1) for i in range(sl - sf + 1)])\n",
    "            if sf >= sl or pf >= pl:\n",
    "                return False\n",
    "            if s[sf] == p[pf] or p[pf] == '?':\n",
    "                return isMatch(s, p, sf + 1, pf + 1)\n",
    "            \n",
    "            return False\n",
    "        return isMatch(s, p, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def isMatch(self, s: str, p: str) -> bool:\r\n",
    "        if s == \"\":\r\n",
    "            return p == \"*\" or p == \"\"\r\n",
    "        if p == \"\":\r\n",
    "            return False\r\n",
    "        match = [[[False, True] for _ in range(len(p)+1)] for _ in range(len(s)+1)]\r\n",
    "        anyset = {\"?\", \"*\"}\r\n",
    "        match[0][0][0] = True\r\n",
    "        for i in range(1, len(s)+1):\r\n",
    "            for j in range(1, len(p)+1):\r\n",
    "                if match[i-1][j-1][0] or (all(match[i][j-1]) and j-2 >= 0 and p[j-2] == '*'):\r\n",
    "                    if s[i-1] == p[j-1] or p[j-1] in anyset:\r\n",
    "                        match[i][j][0] = True\r\n",
    "                if match[i-1][j][0] and p[j-1] == \"*\":\r\n",
    "                    match[i][j][0] = True\r\n",
    "                if not match[i][j][0] and match[i][j-1][0] and p[j-1] == '*':\r\n",
    "                    match[i][j] = [True, False]\r\n",
    "                # print(i, j, match[i][j])\r\n",
    "\r\n",
    "        return match[-1][-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(None)\n",
    "        def helper(i ,j):\n",
    "            if i == -1:\n",
    "                if j == -1:\n",
    "                    return True\n",
    "                return False\n",
    "            if p[i] == '*':\n",
    "                t = i-1\n",
    "                while t>=0 and p[t]=='*':\n",
    "                    t -= 1\n",
    "                if t < 0:\n",
    "                    return True\n",
    "                for k in range(-1, j+1):\n",
    "                    if helper(t, k):\n",
    "                        return True\n",
    "            elif j == -1:\n",
    "                return False\n",
    "            elif p[i] == s[j] or p[i] == '?':\n",
    "                if i == 0 and j == 0:\n",
    "                    return True\n",
    "                return helper(i-1, j-1)\n",
    "            return False\n",
    "        \n",
    "        return helper(len(p)-1, len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        # f[i][j] 表示 s[:i] 与 p[:j] 是否可以匹配\n",
    "        m = len(s)\n",
    "        n = len(p)\n",
    "\n",
    "        f = [[False] * (n+1) for _ in range(m+1)]\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i < 0: \n",
    "                if j < 0: return True\n",
    "                if p[j] == '*': return dfs(i, j-1)\n",
    "                return False\n",
    "            if j < 0:\n",
    "                return i < 0\n",
    "            if p[j] == '*':\n",
    "                return dfs(i, j-1) or dfs(i-1, j-1) or dfs(i-1, j)\n",
    "            elif p[j] == '?' or s[i] == p[j]:\n",
    "                return dfs(i-1, j-1)\n",
    "            return False\n",
    "\n",
    "        return dfs(m-1, n-1)\n",
    "\n",
    "\n",
    "        f[0][0] = True # 两个空字符可以匹配\n",
    "        if p[0] == '*':\n",
    "            for i in range(n):\n",
    "                f[i][0] = True\n",
    "\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if s[i] == p[j] or p[j] == '?':\n",
    "                    f[i+1][j+1] = f[i][j]\n",
    "                elif p[j] == '*':\n",
    "                    f[i+1][j+1] = f[i+1][j] or f[i][j]\n",
    "\n",
    "\n",
    "        return f[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "\n",
    "        n = len(s)\n",
    "        m = len(p)\n",
    "        \n",
    "        @cache \n",
    "        def match(i, j):\n",
    "            print(i, j)\n",
    "            if i == n:\n",
    "                print(\"????\")\n",
    "                for k in range(j, m):\n",
    "                    if p[k] != '*':\n",
    "                        return False \n",
    "                return True\n",
    "            if j == m:\n",
    "                return False \n",
    "            \n",
    "            if p[j] == '?':\n",
    "                \n",
    "                return match(i+1, j+1)\n",
    "            elif p[j] == '*':\n",
    "                if j == m-1:\n",
    "                    return True \n",
    "                res = False \n",
    "                for k in range(i+1, n):\n",
    "                    \n",
    "                    if (p[j+1] in '?*' or s[k] == p[j+1]) and match(k,j+1): # \n",
    "                        \n",
    "                        return True \n",
    "                return match(i, j+1)\n",
    "            else: # english character\n",
    "                return s[i] == p[j] and match(i+1, j+1)\n",
    "\n",
    "        return match(0, 0)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "\n",
    "        n = len(s)\n",
    "        m = len(p)\n",
    "        \n",
    "        @cache \n",
    "        def match(i, j):\n",
    "            if i == n:\n",
    "                for k in range(j, m):\n",
    "                    if p[k] != '*':\n",
    "                        return False \n",
    "                return True\n",
    "            if j == m:\n",
    "                return False \n",
    "            if p[j] == '?':   \n",
    "                return match(i+1, j+1)\n",
    "            elif p[j] == '*':\n",
    "                if j == m-1:\n",
    "                    return True \n",
    "                res = False \n",
    "                for k in range(i+1, n):\n",
    "                    \n",
    "                    if (p[j+1] in '?*' or s[k] == p[j+1]) and match(k,j+1): # \n",
    "                        \n",
    "                        return True \n",
    "                return match(i, j+1)\n",
    "            else: # english character\n",
    "                return s[i] == p[j] and match(i+1, j+1)\n",
    "\n",
    "        return match(0, 0)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "#         def dp(i, j):\n",
    "#             nonlocal m, n\n",
    "#             if i == m and j < n and p[j] == '*':\n",
    "#                 return dp(i, j+1)\n",
    "#             if i == m and j == n:\n",
    "#                 return True\n",
    "#             if (j == n and i < m) or (i == m and j < n) :\n",
    "#                 return False\n",
    "            \n",
    "#             if (i, j) in memo:\n",
    "#                 return memo[(i, j)]\n",
    "#             res = False\n",
    "#             if s[i] == p[j]:\n",
    "#                 res = res or dp(i+1, j+1)\n",
    "#             elif p[j] == '?':\n",
    "#                 res = res or dp(i+1, j+1)\n",
    "#             elif p[j] == '*':\n",
    "#                 res = res or dp(i+1, j) or dp(i, j+1)\n",
    "#             elif s[i] != p[j]:\n",
    "#                 res = False\n",
    "#             memo[(i, j)] = res\n",
    "#             return res\n",
    "        \n",
    "#         m, n = len(s), len(p)\n",
    "#         memo = {}\n",
    "#         return dp(0 ,0)\n",
    "        #####################\n",
    "        def dp(i, j):\n",
    "            nonlocal m, n\n",
    "            if i == m and j == n:\n",
    "                return True\n",
    "            if j == n:\n",
    "                return False\n",
    "            if i == m:\n",
    "                for k in range(j, n):\n",
    "                    if p[k] != '*':\n",
    "                        return False\n",
    "                return True\n",
    "            if (i, j) in memo:\n",
    "                return memo[(i, j)]\n",
    "            res = False\n",
    "            if s[i] == p[j] or p[j] == '?':\n",
    "                res = dp(i+1, j+1)\n",
    "            elif p[j] == '*':\n",
    "                res = dp(i+1, j) or dp(i, j+1)\n",
    "            memo[(i, j)] = res\n",
    "            return res\n",
    "        \n",
    "        temp = []\n",
    "        for i in p:\n",
    "            if i == '*' and temp and temp[-1] == '*':\n",
    "                continue\n",
    "            temp.append(i)\n",
    "        p = ''.join(temp)\n",
    "        m, n = len(s), len(p)\n",
    "        memo = {}\n",
    "        return dp(0 ,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "\n",
    "        m = len(s)\n",
    "        n = len(p)\n",
    "\n",
    "        @cache\n",
    "        def map(i,j):\n",
    "            if i == m or n == j:\n",
    "                if i == m:\n",
    "                    if n == j or p[j:n] == '*' * (n-j):\n",
    "                        return True\n",
    "                return False\n",
    "            \n",
    "            if p[j] == '?':\n",
    "                return map(i+1,j+1)\n",
    "            \n",
    "            elif p[j] == '*':\n",
    "                for k in range(i,m+1):\n",
    "                    if map(k,j+1):\n",
    "                        return True\n",
    "                return False\n",
    "\n",
    "            else:\n",
    "                if s[i] != p[j]:\n",
    "                    return False\n",
    "                return map(i+1,j+1)\n",
    "        \n",
    "        return map(0,0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
